#include <stdlib.h>

//定义节点结构
typedef struct QNode
{
    int   data;   /*数据域*/
    struct QNode   * next;   /*指针域*/
 }QNode, *QueuePtr;

//定义队列结构
 typedef struct
 {
    QueuePtr front;
    QueuePtr rear;
 }queue_t;

void queue_init(queue_t *Q)
{ 
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q->front) exit(0);
    Q->front->next = NULL;
}


void queue_destroy(queue_t *Q)
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
}


void queue_add(queue_t *Q, int e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(0);
    //插入数据
    p->data = e;
    p->next = NULL;
    //Q.rear一直指向队尾
    Q->rear->next = p;
    Q->rear = p;
}

int queue_remove(queue_t *Q)
{
    if(Q->front == Q->rear) return -999999;
    QueuePtr p = Q->front->next;
    int e = p->data;
    Q->front->next = p->next;   //队头元素p出队
    if(Q->rear == p)   //如果队中只有一个元素p, 则p出队后成为空队
    	Q->rear = Q->front;     //给队尾指针赋值
    free(p);   //释放存储空间
    return e;
}

int queue_empty(queue_t *q) 
{
    if(q->front == q->rear) return 1;
    return 0;
}

